# -*- coding: utf-8 -*-

"""剑指 Offer II 077. 链表排序
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？"""

import heapq

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    """可以用快速排序的思路：
    1.取当前链表的首节点作为中间值
    2.重复的操作，因为涉及到下回原料来源与上回，下回操作结果返回上回，形成深度优先的栈式关系，用递归
    
    本地测试通过，说明排序逻辑没有问题
    第一次提交超时，测试用例大量元素值相等
        更改：比较的时候，将等于单独抽出来，形成小于，等于，大于三部分
    第二次提交超时，测试用例为单调链表
        更改：对于每次取首节点作为中间值来说，效率退化到冒泡排序，每次取中间位置的元素作为中间值
        
    综合来看，反正在取参考值的时候，有获取中间位置节点的操作，快速排序还不如归并排序利索。
    同时需要注意的地方，不止要正确处理节点之间的逻辑关系，还需要将不影响逻辑结果的粗糙链表捋干净
    
    两种方法实践下来，内存占用一致，快速排序还是要比归并快些！！！"""
    def sortList(self, head: ListNode) -> ListNode:
        def search_middle(ll):
            quick, slow = ll, ll
            pre = ListNode(next=ll)
            slow_pre = pre
            try:
                while quick:
                    quick = quick.next.next
                    slow_pre = slow_pre.next
                    slow = slow.next
            except AttributeError:
                pass

            if slow is ll:
                slow_pre = None
            # 捋干净粗糙节点
            pre.next = None

            return slow, slow_pre

        def reverse(head):
            if not head.next:
                return head, head

            left, right, equal = ListNode(), ListNode(), ListNode()
            pl, pr, pe = left, right, equal
            
            middle, middle_pre = search_middle(head)
            if middle_pre:
                p = head
                middle_pre.next=middle.next
                middle.next = None
            else:
                p = head.next
                middle.next = None

            while p:
                if p.val > middle.val:
                    pr.next = p
                    p = p.next
                    pr.next.next = None
                    pr = pr.next
                elif p.val < middle.val:
                    pl.next = p
                    p = p.next
                    pl.next.next = None
                    pl = pl.next
                else:
                    pe.next = p
                    p = p.next
                    pe.next.next = None
                    pe = pe.next
            
            equal_head, equal_tail = middle, middle
            if equal.next:
                foo = equal
                equal = equal.next
                foo.next = None
                equal_head.next = equal
                equal_tail = pe
            
            left_head, right_head = None, None
            if left.next:
                left_head, left_tail = reverse(left.next)
            if right.next:
                right_head, right_tail = reverse(right.next)
            
            if left_head and right_head:
                left_tail.next = equal_head
                equal_tail.next = right_head
                return left_head, right_tail
            elif left_head:
                left_tail.next = equal_head
                return left_head, equal_tail
            elif right_head:
                equal_tail.next = right_head
                return equal_head, right_tail
            else:
                return equal_head, equal_tail
        
        if head:
            return reverse(head)[0]
    
    def sortListMerge(self, head: ListNode) -> ListNode:
        def search_middle2(ll):
            quick, slow = ll, ll
            while quick.next:
                quick = quick.next
                if quick.next:
                    quick = quick.next
                    slow = slow.next
            return slow

        def reverse(ll):
            if not ll.next:
                return ll
            
            middle = search_middle2(ll)
            left, right = ll, middle.next
            middle.next = None

            twice = [reverse(left), reverse(right)]

            answer = ListNode()
            p = answer
            pool = [(twice[0].val, 0), (twice[1].val, 1)]
            heapq.heapify(pool)
            while pool:
                _, idx = heapq.heappop(pool)
                p.next = twice[idx]
                p = p.next
                if twice[idx].next:
                    twice[idx] = twice[idx].next
                    heapq.heappush(pool, (twice[idx].val, idx))
                p.next = None
            return answer.next

        if head:
            return reverse(head)
    

def show_ll(ll):
    while ll:
        print(ll.val, end=', ')
        ll=ll.next
        # input('>>')
    print('')


def gen_ll(arr):
    ll = ListNode()
    p = ll
    for v in arr:
        p.next = ListNode(v)
        p = p.next
    return ll.next
    

if __name__ == '__main__':
    so = Solution()
    show_ll(so.sortListMerge(gen_ll([4,2,1,3])))
    show_ll(so.sortListMerge(gen_ll([-1,5,3,4,0])))
    show_ll(so.sortListMerge(gen_ll([])))
    show_ll(so.sortListMerge(gen_ll([-84,142,41,-17,-71,170,186,183,-21,-76,76,10,29,81,112,-39,-6,-43,58,41,111,33,69,97,-38,82,-44,-7,99,135,42,150,149,-21,-30,164,153,92,180,-61,99,-81,147,109,34,98,14,178,105,5,43,46,40,-37,23,16,123,-53,34,192,-73,94,39,96,115,88,-31,-96,106,131,64,189,-91,-34,-56,-22,105,104,22,-31,-43,90,96,65,-85,184,85,90,118,152,-31,161,22,104,-85,160,120,-31,144,115])))
